package com.leetcode.partition3;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/9/16 11:26
 */
public class LC212单词搜索2 {

    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode("");
        for (String word : words) {
            insert(root, word);
        }
        Set<String> answers = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, answers);                //尝试以每个格子为开始查找单词
            }
        }
        return new ArrayList<>(answers);
    }

    public static void main(String[] args) {
//        char[][] board = {{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}};
//        String[] words = {"oath", "pea", "eat", "rain"};
        char[][] board = {{'a', 'b'}, {'a', 'a'}};
        String[] words = {"aba", "baa", "bab", "aaab", "aaa", "aaaa", "aaba"};
        System.out.println(findWords(board, words));            //["aba","aaa","aaab","baa","aaba"]
    }

    private static void dfs(char[][] board, int i, int j, TrieNode cur, Set<String> answers) {
        if (!cur.children.containsKey(board[i][j])) return;             //当前位置在字典树中不存在
        char ch = board[i][j];
        cur = cur.children.get(ch);                            //字符节点存在，指向当前字典树节点

        if (cur.end) answers.add(cur.data);
        board[i][j] = '#';              //标记已经走过
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) continue;          //当前方向不合法
            dfs(board, row, col, cur, answers);
        }
        board[i][j] = ch;               //回溯
    }

    public static void insert(TrieNode root, String word) {
        TrieNode cur = root;
        char[] words = word.toCharArray();
        for (int i = 0; i < words.length; i++) {
            if (cur.children.containsKey(words[i])) {
                if (i == words.length - 1) {
                    TrieNode node = cur.children.get(words[i]);
                    node.end = true;
                    node.data = word;
                }
                cur = cur.children.get(words[i]);
                continue;
            }
            TrieNode trieNode = new TrieNode(null);
            if (i == words.length - 1) {
                trieNode.end = true;
                trieNode.data = word;
            }
            cur.children.put(words[i], trieNode);
            cur = cur.children.get(words[i]);
        }
    }

    private static class TrieNode {
        String data;
        Map<Character, TrieNode> children;
        boolean end;

        public TrieNode(String data) {
            this.data = data;
            children = new HashMap<>();
            end = false;
        }
    }
}
